1. Field of the Invention
The present invention relates to cryptography, and deals more particularly with a system and method for a symmetric key block cipher. This cipher uses multiple stages with a modified Type-3 Feistel network, and a modified Unbalanced Type-1 Feistel network in an expansion box forward function. The cipher allows the block size, key size, number of rounds of expansion, and number of stages of ciphering to vary. The modified Type-3 cipher modifies the word used as input to the expansion box in certain rounds, to speed the diffusion properties of the ciphering.
2. Description of the Related Art
Cryptography is a security mechanism for protecting information from unintended disclosure by transforming the information into a form that is unreadable to humans, and unreadable to machines that are not specially adapted to reversing the transformation back to the original information content. The cryptographic transformation can be performed on data that is to be transmitted electronically, such as an electronic mail message, and is equally useful for data that is to be securely stored, such as the account records for customers of a bank or credit company.
The transformation process performed on the original data is referred to as "encryption". The process of reversing the transformation, to restore the original data, is referred to as "decryption". The terms "encipher" and "decipher" are also used to describe these processes, respectively. A mechanism that can both encipher and decipher is referred to as a "cipher".
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. "Plaintext" refers to the fact that the data is in plain, unencrypted form. "Ciphertext" indicates that the data is in enciphered, or encrypted, form. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the original plaintext block.
A cipher to be used in a computer system can be implemented in hardware, in software, or in a combination of hardware and software. Hardware chips are available that implement various ciphers. Software algorithms are known in the art as well.
Encryption systems fall into two general categories. Symmetric (or secret key) encryption systems use the same secret key for both encrypting and decrypting messages. An example of a symmetric encryption system is the Data Encryption Standard (DES) system, which is a United States federal standard described in NBS FIPS Pub 46. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir, and Adleman.
The category of symmetric encryption systems can be further subdivided into those which operate on fixed size blocks of data (block ciphers), and those which operate on arbitrary length streams of data (stream ciphers).
While there are many methods of symmetric key block encryption, most popular methods are based on Type-2 Feistel Networks. A Type-2 Feistel Network consists of dividing the data to be encrypted into two halves, and then performing some number of rounds, where each round consists of transforming the left half of the data based on the right half of the data, and then transforming the right half based on the modified left half. The two transformations are called subrounds. These transformations must be invertible. That is, it must be possible to perform some set of operations during decryption that will reverse the transformations performed during encryption. In a standard Feistel network, some non-invertible function of one half of the data is simply exclusive-OR'd with the other half, as the exclusive OR operation provides invertibility, but any invertible function may be used in the general case.
Feistel Networks are not limited to this case of dividing the data into two equal halves. Alternatively, in a Type-1 Feistel the data is divided into n equal words, where n&gt;2. If these words are labeled A(1) to A(n), then a full round consists of n subrounds, where each subround consists of transforming word A(i) based on the value of word A(i-1) (with A(1) transformed by A(n)).
Similarly, a Type-3 Feistel can be constructed in which the data is divided into n equal words, where n&gt;2, but in which each word is used to transform more than one (possibly all) of the other words. For example, A(1) could be used to transform A(2), A(3), and A(4) in one subround. A full round consists of n such subrounds.
Feistel based ciphers typically add additional invertible transformations before, and/or after, each full round. For example, some ciphers exclusive-or the entire data block with subkey data before the first round, to complicate certain attacks. "Subkey" refers to using a different key during different rounds, where the subkey values are derived from an input key.
The distinguishing features of different Feistel based ciphers are determined by the choice of the function used to modify a given data word in each subround. Different functions provide different tradeoffs between speed, data size, and security.
Many ciphers, such as DES, base their subround functions on a construct called a substitution box, or S-box, which is an array of data elements. In operation, a cipher block data word is used as an index into the S-box, and the value at that location is then used as the output value. The entries in the S-box are carefully chosen to have good properties for resistance to various attacks, including differential and linear analysis. Some desirable properties of S-boxes include that if the input words vary by one bit, on average, half the output bits should change, so that even small changes in the input data rapidly spread to all the output bits. Also, the entries in the S-box should be chosen to have little correlation to the index, to provide good resistance to linear attacks. While S-box based functions may provide excellent security, they tend to be slow in software implementations, especially on processors with small register sets, due to the costs of index calculation, and the corresponding higher use of register resources.
Other ciphers, such as RC5, base their subround functions on bit-wise rotations, in which one data word is used to specify an amount to rotate the target word. (RC5 is described in "The RC5 Encryption Algorithm", Second International Workshop on Fast Software Encryption, by R. L. Rivest (1995)). Data-dependent rotation provides a very fast subround function, as there are no index calculations and no memory references needed, and all the operations can be kept within the registers. Data-dependent rotations, however, tend to have relatively poor resistance to differential attacks, requiring more rounds to ensure security.
Feistel ciphers tend to be based on length-preserving pseudorandom functions. A length-preserving function is one that takes an input of b bits, and returns a transformed value also having b bits. For example, in a Type-2 Feistel network, where the input block is divided into two halves, b represents the length of each half. Thus as each half is transformed during operation of the cipher, the overall block length of 2b bits is maintained. However, ciphers are also known which do not divide the blocks into components of equal size. These ciphers are referred to as Unbalanced Feistel Networks (UFNs). In a UFN, the block "M" may be described as having some length (s+t). Let L.sub.0 denote the most significant s bits of M (that is, the leftmost s bits), and let R.sub.0 denote the least significant t bits (that is, the rightmost t bits), and assume that s&lt;t. The UFN will process for some number of rounds, where the output message after round i, M.sub.i, can be denoted M.sub.i =L.sub.i.cndot.R.sub.i (where the symbol ".cndot." represents concatenation). The pseudorandom function f.sub.k which is used during each round of the UFN takes as its input an operand having s bits, and returns a value having t bits: that is, f.sub.k is not length-preserving. Using this definition of f.sub.k, the output of round i may be described as M.sub.i =[f.sub.ki (L.sub.i-1).sym.R.sub.i-1 ].cndot.L.sub.i-1 (where exclusive OR is shown as an example of a typical invertible round function). As shown by this definition of f.sub.k, its input operand has s bits, because (L.sub.i-1) is defined as the leftmost s bits. A t-bit result is generated, because f.sub.k is defined as an "s to t" function. This result is then exclusive OR'd (in this example) with the same-sized value R.sub.i-1. Thus, M.sub.i for any value i is formed by concatenating a t-bit operand with an s-bit operand, maintaining the overall length of (s+t). Since f.sub.k expands the number of bits of its input (from s to t), such a function is referred to herein as an "expansion box", or "expansion function".
Examples of ciphers using UFNs are BEAR and LION. These ciphers are described in "Two Practical and Provably Secure Block Ciphers: BEAR and LION", 1996 Workshop on Fast Software Encryption, by R. Anderson and E. Biham (1996). However, these existing UFNs perform a round function that consists of expanding one of the input words, and using this to modify the other words. The word fed into the expansion box for a given round is typically left unchanged by that round. (As shown in the above example, the component (L.sub.i-1) is concatenated without change to form the new rightmost portion of M.)
In view of the above, a stronger, more flexible cipher is needed. One way to make a cipher stronger is to increase the number of rounds of ciphering performed: with each successive transformation, the resulting encryption becomes more difficult to break. Another way to increase the strength is to increase the size of the key. Since the contents of the key remain secret, increasing the size adds another level of difficulty for anyone trying to deduce what transformations may have been performed on the original data, because they are unlikely to guess the random number combination making up the key. Yet another way to increase algorithm strength is to increase the size of the "block" on which the cipher performs its transformations. A block is the unit of original data processed during one ciphering operation. The larger the block size, the more difficult it becomes for an adversary to construct a dictionary of plaintext and matching ciphertext, for a given key, large enough to pose a threat to the security of the algorithm. Further, different keys (i.e., subkeys) can be used for each round, increasing the number of random number combinations that would have to be correctly guessed in order to break the cipher.
It will be appreciated that when a cipher allows varying the number of stages (and therefore the total number of rounds), the key size, the key values, and the block size at the same time, an incredibly difficult challenge is presented to a person attempting to discover the original data contents from an encrypted result. It will also be appreciated that the computations involved to cipher the data are quite complex, and that while performing more rounds of ciphering increases the strength of the result, it also causes computation time to increase. When data is very sensitive, this time spent in ciphering will be warranted. It may be, however, that less sensitive data does not warrant the added time and expense of many rounds of ciphering. By providing an algorithm where the number of rounds of expansion, the number of stages of ciphering, the key size and values, and the block size are variable, the ultimate choice between the level of security required and the amount of computation time utilized rests with the user. By allowing these factors to vary, the cipher of the present invention becomes, in effect, scalable in three dimensions.
Existing symmetric key block ciphers using UFNs may provide for variation in the key size, the block size, and the number of rounds of ciphering, but these ciphers leave unchanged the input word that was fed into the expansion box for each round. Therefore, if the input word is divided into N components, only (N-1) are changed in each round.
Accordingly, a need exists for an improved and more flexible symmetric block cipher which offers excellent resistance to linear and differential attacks; operates quickly and efficiently while using S-boxes; uses an efficient round function; combines the benefits of both Type-1 and Type-3 Feistel networks; uses a UFN with improved mixing properties; and supports a variable length key, variable length block, a variable number of rounds of expansion, and a variable number of stages of ciphering.
The technique of the present invention achieves these objectives while using multiple stages with the fast operations of table lookup, exclusive OR, addition, subtraction, and bitwise rotation, thereby minimizing the time required to encrypt and decrypt data. The mixing properties of the modified Type-3 Feistel which invokes the modified Type- 1 UFN of this technique are increased over typical UFNs by using a feedback in certain rounds. This feedback causes the data word which is used in that round to modify the other data words, left unchanged in typical Feistel UFNs, to also be modified itself. Further, bit-wise rotation is used after certain rounds to further speed the mixing properties of the cipher. The modified Type-1 UFN is implemented as a forward expansion function, which is used during both encryption and decryption. Because this function is a forward function, the necessity of inverting its encryption operations during decryption is removed (thus permitting re-use of the hardware circuit or software routine implementing that function). The UFN uses a novel approach to a Feistel Type-1 network, whereby a word may be used to modify any of the other words of the block, not just the next sequential word of the block. The data-independent sub-keys can be precomputed, further minimizing the time required for encryption and decryption. The S-box can be precomputed as well. A minimal amount of computer storage is required for data used in the operation of the cipher.